package com.michael.tree.btree;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * B树的性质：
 * 1. 每个结点x有下面属性：
 * a. x.n,当前存储在结点x中的关键字个数。
 * b. x.n个关键字本身x.key1, x.key2, ... , x.key(x.n)， 以非降序存放，使得x.key1 <= x.key2 <= ... <=x.key(x.n)
 * c. x.leaf, 一个布尔值，如果x是叶结点，则为true，如果x为内部结点，则为false
 * 2. 每个内部结点x还包含x.n+1个指向其孩子的指针，x.c1, x.c2, ... , x.c(x.n+1)。叶结点没有孩子，所以它们的ci属性没有定义。
 * 3. 关键字x.key1对存储在各子树中的关键字范围加以分隔；如果ki为任意一个存储在以x.ci为根的子树中的关键字，那么
 * k1<=x.key1<=k2<=x.key2<=...<=x.key(x.n)<=k(x.n+1)
 * 4. 每个叶结点具有相同的深度，即树的高度h。（很重要的特性）
 * 5. 每个结点所包含的关键字个数有上界和下界。用一个被称为B树中的最小度数（很重要的特性）的固定证书t>=2表示这些界
 * a. 除了根结点以外的每个结点必须至少有t-1个关键字。因此，除了根结点以外的每个内部结点至少有t个孩子。
 * b. 每个结点至多可包含2t-1个关键字。因此，一个内部结点至多可有2t个孩子。当一个结点恰好有2t-1个关键字，称该结点是满的；
 */
public class BTreeSelf {
    public static int t = 4;

    public static class BNode {
        int n;
        int[] key;
        boolean leaf;
        BNode[] c;

        public BNode() {
            n = 0;
            key = new int[2 * t - 1];
            c = new BNode[2 * t];
            leaf = true;
        }
    }


    private BNode root;

    public BTreeSelf() {
        root = new BNode();
    }

    public int search(BNode x, int k) {
//        int i=1;  //为什么会设置为1
//        while (i<= x.n && k>x.key[i])
//            i=i+1;
//        if (i <= x.n && k == x.key[i])
//          return x.key[i];
//        else if (x.leaf)
//          return 0;
//        else disk-read(x,ci)
//          return search(x.ci,k)
        return 0;
    }

    public void insert(int key) {
        BNode r = root;
        if (r.n == 2 * t - 1) { //说明已满
            BNode s = allocateNode();
            root = s;
            s.leaf = false;
            s.n = 0;
            s.c[0] = r;
            splitChild(s, 0);//分裂
            insertNonFull(s, key);
        } else {
            insertNonFull(r, key);
        }
    }

    /**
     * 分配节点
     */
    private BNode allocateNode() {
        return new BNode();
    }

    /**
     * 分裂
     * x节点为未满节点，而x节点中的子节点c[i]（x.c[i]）节点为满节点，需要将x.c[i]节点进行拆分。<br/>
     * x.c[i]节点中的中间的关键字x.c[i].key[t-1]移到x节点中关键字x.key[i]；<br/>
     * 步骤如下：<br/>
     * 1. 将y=x.c[i]中的拆分成两半，将y.c[t] - y.c[2t-1]->z.c[0] - z.c[t-1]; y.key[t] - y.key[2t-2] -> z.key[0] - z.key[t-2]
     * 2. 将x.key[i] - x.key[n-1] -> x.key[i+1] - x.key[n]; x.c[i+1] - x.c[n] -> x.c[i+2] - x.c[n+1]
     * 3. 将x.key[i] = y.key[t-1]; x.c[i+1] = z
     */
    private void splitChild(BNode x, int i) {
        BNode z = allocateNode();
        BNode y = x.c[i];
        //将y节点中的后半部分的节点以及关键字移到z节点上去；
        z.leaf = y.leaf;
        z.n = t - 1;
        //y.key[t] - y.key[2t-2] -> z.key[0] - z.key[t-2]
        for (int j = 0; j < t - 1; j++) {
            z.key[j] = y.key[j + t];
        }
        if (!y.leaf) {//如果不是叶节点，说明还有子节点，需要移到z节点上去
            //y.c[t] - y.c[2t-1]->z.c[0] - z.c[t-1];
            for (int j = 0; j < t; j++) {
                z.c[j] = y.c[j + t];
            }
        }
        y.n = t - 1;
        //x.c[i+1] - x.c[n] -> x.c[i+2] - x.c[n+1]
        for (int j = x.n + 1; j > i + 1; j--) {
            x.c[j] = x.c[j - 1];
        }
        x.c[i + 1] = z;
        //x.key[i] - x.key[n-1] -> x.key[i+1] - x.key[n]
        for (int j = x.n; j > i; j--) {
            x.key[j] = x.key[j - 1];
        }
        x.key[i] = y.key[t - 1];
        x.n = x.n + 1;
//        DISK-WRITE(y);
//        DISK-WRITE(z);
//        DISK-WRITE(x);
    }

    /**
     * 向未满节点插入
     */
    private void insertNonFull(BNode x, int k) {
        int i = x.n - 1;
        if (x.leaf) {//是叶子结点
            while (i >= 0 && k < x.key[i]) {
                x.key[i + 1] = x.key[i];
                i = i - 1;
            }
            x.key[i + 1] = k;
            x.n = x.n + 1;
        } else {
            while (i >= 0 && k < x.key[i]) {
                i = i - 1;
            }
            i = i + 1;
            if (x.c[i].n == 2 * t - 1) {
                splitChild(x, i);
                if (k > x.key[i]) {
                    i = i + 1;
                }
            }
            insertNonFull(x.c[i], k);
        }
    }

    /**
     * 删除
     * 1. 如果关键字k在节点x中，并且x是叶节点，则从x中删除K
     * 2. 如果关键字k在节点x中，并且x是内部节点，则做一下操作：
     * 2a. 如果节点x中前于k的子节点y至少包含t个关键字，则找出k在以y为根的子树中前驱k'.
     * 递归地删除k'，并在x中用k'代替k。
     * 2b. 对称地，如果y有少于t个关键字，则检查节点x中后于k的子节点z.如果z至少有t个关键字，则找出k在以z为根的子树中后继k'。
     * 递归地删除k'，并在x中用k'代替k.
     * 3c. 否则，如果y和z都只包含t-1个关键字，则将k和z的全部合并进y,这样x就失去k和指向z的指针，并且y现在包含2t-1个关键字。
     * 然后释放z并递归地从y中删除k.
     * 3. 如果关键字k当前不在内部节点x中，则确定必包含k的子树的根x.c[i]（如果k确实在树中）。
     * 如果x.c[i]只有t-1个关键字，必须执行步骤3a或3b来保证降至一个至少包含t个关键字的节点。
     * 然后，通过对x的某个合适的子节点进行递归而结束。
     * 3a. 如果x.c[i]只含有t-1个关键字，但是它的一个相邻的兄弟至少包含t个关键字，
     * 则将x中的某一个关键字降至x.c[i]中，将x.c[i]的相邻左兄弟或右兄弟的一个关键字升至x，将该兄弟中相应的孩子指针移到x.c[i]中，
     * 这样就使得x.c[i]增加了一个额外的关键字。
     * 3b. 如果x.c[i]以及x.c[i]的所有相邻兄弟都只包含t-1个关键字，则将x.c[i]与一个兄弟合并，
     * 即将x的一个关键字移至新合并的节点，使之成为该节点的中间关键字。
     */
    public void delete(BNode x, int k) {
        if (!x.leaf) {
            int idx = findKey(x, k);
            //判断是否找到
            if (idx == x.n) {//意味着没有内部节点没有找到，归为场景3
                int child = findChild(x, k);
                if (x.c[child].n == t - 1) {
                    if (x.c[child - 1].n >= t) {
                        //3a

                    } else if (x.c[child + 1].n >= t) {
                        //3a
                    }else{
                        //3b
                    }
                } else {
                    delete(x.c[child], k);
                }
            } else {//其余是场景2
                if (x.c[idx - 1].n >= t) {//2a——递归删除该左子节点的最大关键k1，然后将该k替换当前节点的k;
                    int k1 = x.c[idx - 1].key[x.c[idx - 1].n - 1];
                    delete(x.c[idx - 1], k1);
                    x.key[idx] = k1;
                } else if (x.c[idx].n >= t) {//2b——递归删除该右子节点的最小关键k1，然后将k替换当前节点的k
                    int k1 = x.c[idx].key[0];
                    delete(x.c[idx], k1);
                    x.key[idx] = k1;
                } else {//3c——将y和z节点进行合并
                    //todo
                }
            }
        } else {
            BNode y = Preceding_Child(x);//前继节点
            BNode z = Successor_Child(x); //后继节点
//        22.		 w ← root(x)
//        23.		 v ← RootKey(x)
//        24.			if n[x] > t − 1 then Remove-Key(k, x)
//        25.			else if n[y] > t − 1 then
//        26.				k' ← Find-Predecessor-Key(w, v)
//        27.				Move-Key(k', y,w)
//        28.				k' ← Find-Successor-Key(w, v)
//        29.				Move-Key(k',w, x)
//        30.				B-Tree-Delete-Key(k, x)
//        31.			else if n[w] > t − 1 then
//        32.				k' ← Find-Successor-Key(w, v)
//        33.				Move-Key(k', z,w)
//        34.				k' ← Find-Predecessor-Key(w, v)
//        35.				Move-Key(k',w, x)
//        36.				B-Tree-Delete-Key(k, x)
//        37.			else
//        38.				s ← Find-Sibling(w)
//        39.				w' ← root(w)
//        40.					if n[w'] = t − 1 then
//        41.						Merge-Nodes(w',w)
//        42.						Merge-Nodes(w, s)
//        43.						B-Tree-Delete-Key(k, x)
//        44.					else
//        45.						Move-Key(v,w, x)
//        46.						B-Tree-Delete-Key(k, x)
        }
    }

    /**
     * 查找x节点的相邻左节点，也就是x节点的前继节点
     */
    private BNode Preceding_Child(BNode x) {
        return new BNode();//todo
    }

    /**
     * 查找x节点的相邻右节点，也就是x节点的后继节点
     */
    private BNode Successor_Child(BNode x) {
        return new BNode();//todo
    }

    /**
     * 查询关键字k在该节点是否存在
     */
    int findKey(BNode x, int k) {
        int idx = -1;
        while ((++idx) < x.n && x.key[idx] == k) {
            return idx;
        }
        return idx;
    }

    int findChild(BNode x, int k) {
        int idx = -1;
        while ((++idx) < x.n && x.key[idx] < k) {
            return idx;
        }
        return idx;
    }

    public static void main(String[] args) {
        IntStream stream = Arrays.stream(new int[]{5, 1, 3, 2, 4, 20, 36, 45, 21, 10, 23, 6, 85, 65});
        BTreeSelf bTreeSelf = new BTreeSelf();
        stream.forEach(item -> bTreeSelf.insert(item));
        System.out.println("bTreeSelf = " + bTreeSelf);
    }
}
